package william.array;

/**
 * @author ZhangShenao
 * @date 2024/3/2
 * @description <a href="https://leetcode.cn/problems/container-with-most-water/description/">...</a>
 */
public class Leetcode11_盛水最多的容器 {
    /**
     * 采用指针对撞法
     * 记录最大面积
     * 同时从首、尾两端开始遍历数组,计算两个高度所组成的面积,并更新最大面积
     * 之后将指针向中间移动,因为盛水的面积取决于短板,因此如果将长板向中间移动,则一定会缩小面积,因此每次都将短板向中间移动
     * <p>
     * 时间复杂度O(N) 只遍历数组一次
     * 空间复杂度O(1)
     */
    public int maxArea(int[] height) {
        //边界条件校验
        if (height == null || height.length < 2) {
            return 0;
        }

        //记录最大面积
        int maxArea = 0;

        //采用指针对撞法,遍历数组
        int l = 0;
        int r = height.length - 1;
        while (l < r) {
            //计算面积
            int h = Math.min(height[l], height[r]);
            int len = r - l;
            int area = h * len;
            maxArea = Math.max(maxArea, area);

            //根据短板原则,将较小的高度向中间移动
            if (height[l] <= height[r]) {
                l++;
            } else {
                r--;
            }
        }


        //返回最大面积
        return maxArea;
    }
}
